package gold.gold03;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

/**
 *
 */
public class S0808有重复字符串的排列组合 {
    /**
     * 66, 看了一下上一题才知道这一题怎么写, 这个swap, 表示在那个位置填充上指定的值
     * 比较经典的题目。就是不太知道这个重复怎么写, 用set去重吗。因为是String[], 可以考虑一下流操作去重。
     *
     */
    public String[] permutation(String S) {
        if(S == null || S.length() == 0) return new String[]{};
        char[] charArray = S.toCharArray();
        List<String> resList = new LinkedList<>();
        permutationHelp(resList, charArray, 0);
        String[] res = new String[resList.size()];
        int count = 0;
        for(String tempString: resList){
            res[count++] = tempString;
        }
        return res;
    }
    private void permutationHelp(List<String> resList, char[] charArray, int posi){
        // 这里这个add的位置, 非常绝妙, 注意不是在下面那个for里面add的, 在这里add才表示真正确定了一种排列。
        // 即每一次交换只是为了确定一个位置上的char, 后面的还没确定, 到最后才算是确定了。
        if(posi == charArray.length - 1){
            resList.add(new String(charArray));
            return ;
        }
        Set<Character> charSet = new HashSet<>();
        // 防止进去了同样的char。
        for(int i = posi; i < charArray.length; i++){
            charSet.add(charArray[i]);
        }
        for(int i = posi; i < charArray.length; i++){
            if(charSet.contains(charArray[i])){

                swapCharArray(charArray, posi, i);
                // resList.add(new String(charArray));
                permutationHelp(resList, charArray, posi + 1);
                swapCharArray(charArray, posi, i);
                charSet.remove(charArray[i]);
            }
        }
    }
    private void swapCharArray(char[] charArray, int a, int b){
        char temp1 = charArray[a];
        charArray[a] = charArray[b];
        charArray[b] = temp1;
    }
}
